The problem is missing one specific information that the input can produce disconnected multiple graphs, which should be a huge point. I could not figure out why my answer was marked wrong until I looked up the solution.

Surprising thing is others providing answers as if that is not a concern.

This is actually variant of Hungarian Algorithm.

Isn't this approach a BFS? The title says DFS, but I'm really confused as it appears to be BFS

Similar logic. I did it in both BFS and the recursive DFS. Know both to crack the coding interviews.💪🏻

"""
    1st approach: BFS + nodes coloring

    Time    O(V+E)
    Space   O(V)
    156 ms, faster than 62.09%
"""


class Solution(object):
    def isBipartite(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: bool
        """
        seen = {}
        # we need to check every node because it is possible that graph[0] doesn't have any vertices connected
        for i in range(len(graph)):
            if i not in seen:
                if self.check(graph, i, seen) == False:
                    return False
        return True

    def check(self, graph, start, seen):
        q = [(start, 1)]
        while len(q) > 0:
            pop, color = q.pop(0)
            if pop in seen:
                if seen[pop] != color:
                    return False
                continue
            seen[pop] = color
            vertices = graph[pop]
            for v in vertices:
                q.append((v, -color))
        return True


"""
    2nd approach: recursive DFS + nodes coloring

    Time    O(V+E)
    Space   O(V)
    164 ms, faster than 40.67%
"""


class Solution(object):
    def isBipartite(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: bool
        """
        seen = {}
        # we need to check every node because it is possible that graph[0] doesn't have any vertices connected
        for i in range(len(graph)):
            if i not in seen:
                if self.check(graph, i, 1, seen) == False:
                    return False
        return True

    def check(self, graph, node, color, seen):
        if node in seen:
            if seen[node] != color:
                return False
            return True
        seen[node] = color
        vertices = graph[node]
        for v in vertices:
            if self.check(graph, v, -color, seen) == False:
                return False
        return True

BTW, here is another question we can use the similar approach, #886 , practice them in a row to get familiar with this type of questions

Why do you use stack?

Thanks for the article!
For some reason I assumed, that all nodes are connected, and started with a just queue(/stack), missing the first for-loop.

So is there any difference between the time and space complexity of the DFS approach and the BFS approach?

Could someone please explain how the graph is represented in the description. How does [[1,3], [0,2], [1,3], [0,2]] turn to
0----1
| |
| |
3----2

Here is the bfs and dfs solutions.
DFS:

class Solution {
    public boolean isBipartite(int[][] graph) {
        Set<Integer> A = new HashSet<>();
        Set<Integer> B = new HashSet<>();
        for (int i = 0; i < graph.length; i++) {
            if (!A.contains(i) && !B.contains(i)) {
                A.add(i);
                if (!dfs(graph, i, A, B)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    boolean dfs(int[][] graph, int node, Set<Integer> A, Set<Integer> B) {
        for (int i = 0; i < graph[node].length; i++) {
            if (!A.contains(graph[node][i]) && !B.contains(graph[node][i])) {
                if (A.contains(node)) {
                    B.add(graph[node][i]);
                }
                else {
                    A.add(graph[node][i]);
                }
                if (!dfs(graph, graph[node][i], A, B)) {
                    return false;
                }                
            }
            else {
                if ((A.contains(node) && A.contains(graph[node][i])) || (B.contains(node) && B.contains(graph[node][i]))) {
                    return false;
                }
            }
        }
        return true;
    }
}

BFS:

class Solution {
    public boolean isBipartite(int[][] graph) {
        int[] color = new int[graph.length];
        Arrays.fill(color, -1);
        for (int i = 0; i < graph.length; i++) {
            if (color[i] == -1 && !bfs(graph, color, i)) {
                return false;
            }
        }
        return true;
    }
    
    boolean bfs(int[][] graph, int[] color, int node) {
        Queue<Integer> queue = new LinkedList<Integer>();
        color[node] = 0;
        queue.add(node);
        while (!queue.isEmpty()) {
            int n = queue.poll();
            for (int i = 0; i < graph[n].length; i++) {
                if (color[graph[n][i]] == -1) {
                    color[graph[n][i]] = color[n] ^ 1;
                    queue.add(graph[n][i]);
                }
                else {
                    if (color[graph[n][i]] == color[n]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

There is no need to create new stack for every iteration.